package LC;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @ClassName Lc39
 * @Description: TODO
 * @Author hl
 * @Date 2021/4/22
 * @Version V1.0
 **/
public class Lc39 {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        if(candidates==null||candidates.length==0) return res;
        List<Integer> list=new ArrayList<>();
        seach(res,list,target,0,candidates);
        return res;
    }

    public static void seach(List<List<Integer>> res, List<Integer> list, int target,int index,int []candidates ) {
        if(index==candidates.length) return;
        if(target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        seach(res,list,target,index+1,candidates);
        if(target-candidates[index]>=0){
            list.add(candidates[index]);
            seach(res,list,target-candidates[index],index,candidates);
            list.remove(list.size()-1);
        }

    }

    public static void main(String[] args) {
        int []candidates = {2,3,6,7};
        int target = 7;
        List< List<Integer> >res=combinationSum(candidates,target);
        System.out.println(res.toString());
    }
}
